package offer.algorithm;


import java.util.Stack;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/20 16:38
 */
public class StackPopOrder22 {

    public static <T> boolean isStackOrder(T[] pushOrder, T[] popOrder) {
        if (pushOrder.length != popOrder.length)
            return false;
        Stack<T> oriStack = new Stack<>();
        int index = 0;
        for (int i = 0; i <= pushOrder.length; ) {
            if (oriStack.isEmpty()) {
                if (i >= pushOrder.length)
                    break;
                else {
                    oriStack.push(pushOrder[i]);
                    ++i;
                }
            } else {
                if (!oriStack.peek().equals(popOrder[index])) {
                    if (i >= pushOrder.length)
                        break;
                    oriStack.push(pushOrder[i]);
                    ++i;
                } else {
                    oriStack.pop();
                    ++index;
                }
            }
        }
        if (index >= popOrder.length)
            return true;
        return false;
    }


    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0, length = popA.length;
        while (i <= length && j < length) {
            if (!stack.isEmpty() && popA[j] == stack.peek()) {
                stack.pop();
                j++;
            } else {
                if (i == length)
                    return false;
                stack.push(pushA[i++]);
            }
        }
        return i == j;
    }

    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5};
        int[] B = {4, 5, 3, 1, 2};

        boolean b = IsPopOrder(A, B);
        System.out.println(b);

    }

}
